package acwing.算法进阶打卡;/**
 * @author： li
 * @date： 2022-04-07 15:05
 * @version 1.0
 */

import java.util.Scanner;

/**
 * @author： ljm
 * @date： 2022-04-07 15:05
 * @version 1.0
 */
public class 线性筛 {
    static int N = 1000010,cnt;
    static int[] primes = new int[N]; //题目本意是求素数个数，当然也能求每个数的最小质因子
    static boolean[] st = new boolean[N];

    static void get_primes(int n){
        for(int i = 2; i <= n; i++){
            if(!st[i]) primes[++cnt] = i;
            for(int j = 1; primes[j] <= n/i; j ++){
                st[primes[j]*i] = true;
//                System.out.format("st[%d] = true,st[%d*%d] i = %d\n",primes[j]*i,primes[j],i,i); //输出语句
                if(i % primes[j] == 0) break;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        get_primes(n);
        for(int i=2;i<=n;i++){
            if(!st[i])
                System.out.print(primes[i]+" ");
        }
        System.out.println(cnt);
    }
}
